David Kemp
Abstract:
In this talk, we investigate auction mechanisms for combinatorialreverse auctions. The model is that selfish agents own elements, and the auctioneer wants to purchase a feasible set for some problem from the agents. The specific problems that we study are:
1. Vertex Cover: The agents own the vertices of a graph, and the auctioneer wants to purchase a vertex cover from them.
2. k-Flow: The agents own edges, and the auctioneer wants to buy kedge-disjoint paths from a source to a sink.
3. Cut: The agents own edges, and the auctioneer wants to purchase an s-t cut.
In such settings, it is commonly assumed that selfish agents will act in such a way as to maximize their own profit; in particular, this may include misrepresenting their true cost for letting the auctioneer use their resources (edges or vertices). Thus, mechanisms should have severable desirable properties.
1. Truthfulness: selfish agents want to reveal their true costs.
2. Frugality: the mechanism does not pay much more than "necessary" to achieve truthfulness.
3. Computability: the mechanism can be computed in polynomial time.
We begin this talk with a brief introduction to auctions, truthfulness, and the notion of frugality. After presenting a novel and optimal mechanism for Vertex Cover, we show how to use the Vertex Cover mechanism as a useful design methodology for other problems, by deriving from it competitive mechanisms for flows and cuts.We end with a number of interesting open problems.
(Joint work with Mahyar Salek and Cristopher Moore, which appeared in FOCS 2010; this talk will also discuss an independent FOCS 2010 paper by Ning Chen, Edith Elkind, Nick Gravin, and Fedor Petrov, including the similarities and differences between the ideas.)